package strings;

import javafx.util.Pair;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by Tzachi on 24/10/2014.
 * Given a string, find the minimum window containing a given set of characters
 */
public class MinimumWindow {
    // Returns null if no valid window is found. Else returns minWindowBegin and minWindowEnd pair
    // with the starting and ending position of the minimum window.
    public Pair<Integer, Integer> minWindow(char[] S, char[] T) {

        int minWindowBegin = -1;
        int minWindowEnd = -1;

        int sLen = S.length;
        int tLen = T.length;

        // hash table init all to 0s
        // used to check how many letters left in T to be filled
        // TODO: replace with hash table
        int[] needToFind = new int[256];

        for (int i = 0; i < tLen; i++) {
            needToFind[T[i]]++;
        }

        // TODO: replace with hash table
        int[] hasFound = new int[256];

        int minWindowLen = Integer.MAX_VALUE;
        int count = 0;
        for (int begin = 0, end = 0; end < sLen; end++) {
            // skip characters not in T
            if (needToFind[S[end]] == 0) {
                continue;
            }

            hasFound[S[end]]++;
            if (hasFound[S[end]] <= needToFind[S[end]])
                count++;

            // if window constraint is satisfied
            if (count == tLen) {
                // advance begin index as far right as possible,
                // stop when advancing breaks window constraint.
                while (needToFind[S[begin]] == 0 ||
                        hasFound[S[begin]] > needToFind[S[begin]]) {
                    if (hasFound[S[begin]] > needToFind[S[begin]])
                        hasFound[S[begin]]--;
                    begin++;
                }

                // update minWindow if a minimum length is met
                int windowLen = end - begin + 1;
                if (windowLen < minWindowLen) {
                    minWindowBegin = begin;
                    minWindowEnd = end;
                    minWindowLen = windowLen;
                } // end if
            } // end if
        } // end for

        return (count == tLen) ? new Pair<>(minWindowBegin, minWindowEnd) : null;
    }

    public static void main(String[] args) {
        String[] s;
    }
}
